Search Results

Documents authored by Chan, David Yu Cheng

Found 2 Possible Name Variants:

Chan, David Yu Cheng

Document
DOI: 10.4230/LIPIcs.DISC.2017.12
On the Number of Objects with Distinct Power and the Linearizability of Set Agreement Objects

Authors: David Yu Cheng Chan, Vassos Hadzilacos, and Sam Toueg

Published in: LIPIcs, Volume 91, 31st International Symposium on Distributed Computing (DISC 2017)

Abstract
We first prove that there are uncountably many objects with distinct computational powers. More precisely, we show that there is an uncountable set of objects such that for any two of them, at least one cannot be implemented from the other (and registers) in a wait-free manner. We then strengthen this result by showing that there are uncountably many linearizable objects with distinct computational powers. To do so, we prove that for all positive integers n and k, there is a linearizable object that is computationally equivalent to the k-set agreement task among n processes. To the best of our knowledge, these are the first linearizable objects proven to be computationally equivalent to set agreement tasks.
Cite as

David Yu Cheng Chan, Vassos Hadzilacos, and Sam Toueg. On the Number of Objects with Distinct Power and the Linearizability of Set Agreement Objects. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 12:1-12:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{chan_et_al:LIPIcs.DISC.2017.12,
  author =	{Chan, David Yu Cheng and Hadzilacos, Vassos and Toueg, Sam},
  title =	{{On the Number of Objects with Distinct Power and the Linearizability of Set Agreement Objects}},
  booktitle =	{31st International Symposium on Distributed Computing (DISC 2017)},
  pages =	{12:1--12:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-053-8},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{91},
  editor =	{Richa, Andr\'{e}a},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017.12},
  URN =		{urn:nbn:de:0030-drops-79973},
  doi =		{10.4230/LIPIcs.DISC.2017.12},
  annote =	{Keywords: Set Agreement, Asynchronous System, Shared Memory}
}

Yu, Changyuan

Document
DOI: 10.4230/LIPIcs.STACS.2008.1314
An Improved Randomized Truthful Mechanism for Scheduling Unrelated Machines

Authors: Pinyan Lu and Changyuan Yu

Published in: LIPIcs, Volume 1, 25th International Symposium on Theoretical Aspects of Computer Science (2008)

Abstract
We study the scheduling problem on unrelated machines in the mechanism design setting. This problem was proposed and studied in the seminal paper (Nisan and Ronen 1999), where they gave a $1.75$-approximation randomized truthful mechanism for the case of two machines. We improve this result by a $1.6737$-approximation randomized truthful mechanism. We also generalize our result to a $0.8368m$-approximation mechanism for task scheduling with $m$ machines, which improve the previous best upper bound of $0.875m( Mu'alem and Schapira 2007)
Cite as

Pinyan Lu and Changyuan Yu. An Improved Randomized Truthful Mechanism for Scheduling Unrelated Machines. In 25th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 1, pp. 527-538, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{lu_et_al:LIPIcs.STACS.2008.1314,
  author =	{Lu, Pinyan and Yu, Changyuan},
  title =	{{An Improved Randomized Truthful Mechanism for Scheduling Unrelated Machines}},
  booktitle =	{25th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{527--538},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-06-4},
  ISSN =	{1868-8969},
  year =	{2008},
  volume =	{1},
  editor =	{Albers, Susanne and Weil, Pascal},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2008.1314},
  URN =		{urn:nbn:de:0030-drops-13146},
  doi =		{10.4230/LIPIcs.STACS.2008.1314},
  annote =	{Keywords: Truthful mechanism, scheduling}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact